This invention generally relates to tracking relative motion between a device and an adjacent surface using an optical detector circuit that responds to changes in images of the surface, and more specifically, to producing a signal indicative of the relative motion as a function of a cross correlation between a reference image and a comparison image, and an auto correlation of the reference image, where only pixel data for the reference image are retained in a memory.
A xe2x80x9cmechanicalxe2x80x9d mouse is the most common type of pointing device used for controlling a cursor and other graphic components on a computer display. Typically, to detect the motion of the mouse over a surface, a ball captured within a cavity on the bottom of the mouse contacts the surface and rotates as the mouse is moved over the surface by the user. The rotational movement of the ball in the cavity is transferred to two rollers that contact the ball. Shafts on which the rollers are mounted are coupled to rotary motion encoders. The rollers are orthogonally positioned relative to each other so that signals from the encoders correspond to orthogonal X axis and Y axis components of motion, where these two axes are determined relative to the mouse orientation. The xcex94X and xcex94Y components of motion derived from the encoder signals are input to a personal computer (PC) or other computing device through a serial port, a personal system/2 (PS/2) port, a bus mouse port, or a universal serial bus (USB) port and used to control a cursor or other graphical object on a display screen. A mouse also usually includes two or more switches that produce state signals when actuated by a user and may include a rotary wheel that is coupled to yet another rotational encoder and a state switch for controlling scrolling of the contents of a display window and/or other functions. A related type of pointing device called a xe2x80x9ctrack ballxe2x80x9d also employs a ball to actuate rotational encoders, but the ball is exposed on the upper surface of this pointing device so that it is movable by the user""s fingers or hand, while the housing in which the ball is captive remains generally fixed in position.
The mechanical mouse described above can produce an erratic signal if the ball and rotational encoder rollers are not periodically cleaned to remove deposits that tend to buildup where the rollers contact the ball. Also, the ball may not roll properly over a slick surface, causing errors in tracking the motion of the mouse. More recently, an xe2x80x9copticalxe2x80x9d mouse has been developed that avoids most of the problems associated with the use of a rotatable ball in a mechanical mouse. In contrast to a mechanical mouse, an optical mouse does not include a rotatable ball in the mouse, but instead tracks the motion of the mouse by imaging the surface over which the mouse is being moved. An earlier version of an optical mouse sold by Mouse Systems, Inc. employed a special mouse pad having a reflective surface and included an orthogonal grid of closely spaced lines. Motion of this earlier type of optical mouse was detected by sensing the variations in the intensity of light reflected from the special surface, caused by the grid lines, and interpolating to resolve motion with a greater resolution than the grid spacing. In contrast, a more recently developed optical mouse sold by Microsoft Corporation is able to track movement of the device over most surfaces, thereby eliminating the need for any special surface or pad. Details of this type of optical mouse are disclosed in commonly assigned U.S. Pat. No. 6,172,354, which issued on Jan. 9, 2001. To detect motion, the optical mouse described in this patent employs a red light emitting diode (LED) source to illuminate the adjacent surface over which the mouse is being moved. A two-dimensional array of variable sensitivity photo detectors (i.e., an artificial retina) in the base of the optical mouse produces a pixel image of a portion of the surface in response to the red light reflected from the surface. The image signals from the photo detectors are periodically stored as pixel data in two different image buffers. These data are processed to determine a cross correlation from which a xcex94X component and xcex94Y component of the mouse movement can be determined as a function of the cross correlation results.
Two image buffers are used in the prior art optical mouse to determine the cross correlation, including one that stores an Nxc3x97N pixel reference frame image, and another that stores an Mxc3x97M comparison frame image of the portion of the surface over which the mouse is moved. Each pixel in a region of interest in the reference frame is read and compared with all pixels in the region of interest in the comparison frame to determine a cross correlation of the two image buffers. The result of this comparison is input to a correlation array. Each component of the correlation array includes the sum of the differences for a different offset between the comparison and reference frames. The differences are accumulated by processing the pixels stored in the comparison frame buffer against those stored in the reference frame buffer, which generally requires a total of Mxc3x97Mxc3x97Nxc3x97N operations, as typically implemented in the prior art. As a result, the process to determine cross correlation in this prior art approach is both slow and computationally intensive. In addition, the process requires that two relatively expensive, moderately large memory arrays be provided to store the reference image frame and the comparison image frame data. All processing is done within circuitry included in the mouse, so that the signal sent to the computer for use in controlling a cursor of other portions of a display in response to the movement of the optical mouse is generally equivalent to that produced by a mechanical mouse. The movement signal is formatted to connect to a PS/2 port or a USB port. The maximum velocity of mouse movement that this prior art optical sensing system can accurately track is about 18 inches/sec.
Image recognition systems typically use cross correlation and auto correlation to determine the disposition of an object relative to a background. Such systems also normally use two memory arrays, one to store a reference image frame and another to store a comparison image frame, just as in the optical mouse currently sold by Microsoft Corporation. To reduce the cost of an optical mouse, it would be preferable to employ an application specific integrated circuit (ASIC) processing chip within the mouse that does not require two distinct memory arrays to store the reference and comparison frames used to determine cross correlation. It would be desirable to achieve better tracking performance by using such an optical mouse and desirable to determine the movement of the mouse using sub-pixel interpolation.
Accordingly, there is clearly motivation to develop a new approach for determining correlation that can achieve the desired more efficient tracking capability, with less demand for processing cycles, and at a lower cost than the current approach. This new approach should also achieve a lower cost by using only a single buffer memory rather than the two memory arrays normally required in calculating correlation.
In a pointing device that employs an optical imaging sensor for monitoring movement relative to a surface, successive image frames are compared to determine the direction and extent of the movement. The imaging sensor produces a signal corresponding to pixel image data for the adjacent surface. Image data for a reference frame are stored in a specialized memory buffer for use in determining a cross correlation with a comparison frame that is subsequently acquired by imaging the surface. Successive pixels of the comparison frame are processed to determine components of the cross correlation as the reference frame data are shifted through the buffer memory. Each component of the cross correlation represents the absolute value of a difference between a pixel of the comparison frame and pixels around a related pixel in the reference frame, and these components correspond to the various different directions in which the relative movement might occur. The cross correlation component having the minimum value indicates the direction of the relative movement.
In a conventional approach to determining the relative movement between an object and an adjacent surface, a separate memory array would be provided for storing successive comparison frames and for storing a reference frame. However, in the present invention, only the reference frame is stored in memory. As a result, the cost of the pointing device is substantially reduced since it is not necessary to provide a memory array for the comparison frame. Instead, the image data for the successive comparison frames are processed a pixel at a time, as the data are read from the imaging sensor, so there is no need to retain the image data for a comparison framexe2x80x94unless used to provide a new reference frame.
The present invention also includes the step of determining an auto correlation using the image data for the reference frame stored in the memory buffer. A sub-pixel interpolation of the relative movement is then determined as a function of the auto (and cross) correlation. Also, since auto correlation is determined in parallel with cross correlation, processing of the image data is very efficient. As each pixel in the image data for the comparison frame is read from the imaging sensor, the buffer memory is selectively reloaded with image data for the reference frame that was previously loaded therein. The image data for the reference frame are shifted through the buffer memory as successive pixels of the comparison frame are read from the imaging sensor. However, at times, it will be necessary to load the buffer memory with a new reference frame using the image data for the comparison frame that is currently being read from the imaging sensor. Since the relative movement between the pointing device and the surface is monitored over time, the velocity of the relative movement is readily calculated in the pointing device. The buffer memory is then loaded with image data from the comparison frame as necessary to ensure that a meaningful cross correlation can be determined in subsequent frames. The need to load a new reference frame into the buffer memory is determined as a function of the velocity of motion. Specifically, the relative position is extrapolation by adding a distance corresponding to the velocity to the current position. For example, the position one frame away can be approximated by using the velocity to determine the distance that will be traveled during the time for the next frame to be acquired to the current position. The intent is to load a new reference frame into the buffer memory before the relative movement between the pointing device and the surface is sufficient to cause a subsequent comparison frame to no longer overlap the reference frame previously stored in the buffer memory.
Additional temporary storage is provided in the buffer memory for the last portion of the image data of a previous reference frame, so that the last portion of the image data of the previous reference frame remains available for use in determining the cross correlation as the image data for the current reference frame are loaded into the buffer memory to become the new reference frame. Image data for the previous reference frame are discarded as the new reference frame is loaded.
Another aspect of the present invention is directed to machine readable medium that stores a plurality of machine instructions for performing the steps of the method described above.
Yet another aspect of the present invention is directed to a pointing device that produces an output signal indicative of a relative movement between at least a portion of the pointing device and an adjacent surface. The pointing device includes an imaging detector that produces a signal corresponding to an image of the adjacent surface, an electronic switch having a first input to receive the signal from the imaging detector and a second input, a sequential memory buffer, and a processing circuit that generally carries out the steps of the method described above.
A still further aspect of the present invention is directed to a method for determining a sub-pixel interpolation component of the relative movement between an object and an adjacent surface. In this method, a signal corresponding to a pixelated image of the surface is produced, and a reference frame for the surface that includes data for each of a plurality of pixels of the pixelated image is stored in memory. As relative movement occurs between the object and the adjacent surface, a comparison frame is produced that includes data for a plurality of pixels in a new pixelated image. The cross correlation between the data for the reference frame and the data for the comparison frame, as well as an auto correlation of the data in the reference frame are then determined. Finally, the sub pixel interpolation component of the relative movement is determined as a function of both the cross correlation and the auto correlation.